// 给定整数数组arr，再给定一个整数k，要求返回数组arr中最小的k个数

// 思路1，堆排序，构造大小为k的大顶堆，比较[k, arr.length - 1]的每个元素和大顶堆的arr[0],如果小于则交换位置进行heapify
// 时间复杂度：O(nlogk)
// 空间复杂度：O(1)

function smallestK(arr, k) {
    function buildMaxHeap(arr, k) {
        for (let i = Math.floor((k - 2) / 2); i >= 0 ; i--) {
            heapify(arr, i, k - 1)            
        }
    }
    function heapify(arr, start, end) {
        let leftIndex = 2 * start + 1
        let rightIndex = leftIndex + 1
        while (leftIndex <= end) {
            console.log(11)
            let resIndex = start
            if (arr[leftIndex] > arr[resIndex]) {
                resIndex = leftIndex
            }
            if (rightIndex <= end && arr[rightIndex] > arr[resIndex]) {
                resIndex = rightIndex
            }
            if (resIndex === start) {
                break
            }
            [arr[resIndex], arr[start]] = [arr[start], arr[resIndex]];
            start = resIndex
            leftIndex = 2 * start + 1
            rightIndex = leftIndex + 1
        }
    }
    buildMaxHeap(arr, k)
    for (let i = k; i < arr.length; i++) {
        if (arr[i] < arr[0]) {
            [arr[i], arr[0]] = [arr[0], arr[i]];
            heapify(arr, 0, k - 1)
        }        
    }
    return arr.slice(0, k)
}
let arr = [3, 8, 5, 4, 7, 9, 2, 1]
let k = 2
console.log(smallestK(arr, k))
// 思路2，利用快排，每次确定一个基准的位置，假如这个位置等于k，或者
// 时间复杂度：O(n)
// 空间复杂度：O(logn)

function smallestK(arr, k) {
    function quickSort(arr, left, right) {
        if (left < right) {
            let index = partition(arr, left, right)
            if (index === k) {
                return arr.slice(0, k)
            } else if (index > k) {
                quickSort(arr, left, index - 1)
            } else {
                quickSort(arr, index + 1, right)
            }
        }
        return arr.slice(0, k)
    }

    function partition(arr, left, right) {
        let pivot = Math.floor(Math.random() * (right - left)) + left
        let pivotVal = arr[pivot];
        [arr[left], arr[pivot]] = [arr[pivot], arr[left]];
        let i = left + 1
        for (let j = i; j <= right; j++) {
            if (arr[j] < pivotVal) {
                [arr[i], arr[j]] = [arr[j], arr[i]];
                i++
            }
        }
        [arr[left], arr[i - 1]] = [arr[i-1], arr[left]];
        return i - 1
    }
    return quickSort(arr, 0, arr.length - 1)
}

let arr1 =  [3, 8, 5, 4, 7, 9, 2, 1]
let k1 = 2
console.log(smallestK(arr1, k1));